#include <vector>
#include <queue>
#include <functional>

using namespace std;

// 参加会议的最多员工数
// 一个公司准备组织一场会议，邀请名单上有 n 位员工
// 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
// 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
// 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
// 每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
// 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
// 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/


// 内向基环树
class Solution 
{
public:
    int maximumInvitations(vector<int>& g) 
    {
        int n = g.size();
        vector<vector<int>> rg(n); // g 的反图
        vector<int> deg(n);
        for(int x = 0; x < n; ++x)
        {
            int y = g[x];
            rg[y].push_back(x);
            ++deg[y];
        }

        queue<int> q;
        for(int x = 0; x < n; ++x)
        {
            if(deg[x] == 0) q.push(x);
        }
        // 利用拓扑排序将图删到只剩下环
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            int y = g[x];
            if(--deg[y] == 0) q.push(y);
        }

        // 通过反图 rg 寻找树枝上最深的链
        function<int(int)> rdfs = [&](int x)
        {
            int maxDepth = 1;
            for(int y : rg[x])
            {
                if(deg[y] == 0) maxDepth = max(maxDepth, rdfs(y) + 1);
            }
            return maxDepth;
        };

        int maxRingSize = 0, sumChainSize = 0;
        for(int i = 0; i < n; ++i)
        {
            if(deg[i] <= 0)
            {
                continue;
            }

            // 遍历基环上的点（拓扑排序后入度大于 0）
            deg[i] = -1;
            int ringSize = 1;
            // y == i 表示回到了原点，基环遍历完毕
            for(int y = g[i]; y != i; y = g[y])
            {
                deg[y] = -1; // 将基环上的点的入度标记为 -1，避免重复访问
                ++ringSize;
            }
            if(ringSize == 2) sumChainSize += rdfs(i) + rdfs(g[i]); // 基环大小为 2，累加两条最长链的长度
            else maxRingSize = max(maxRingSize, ringSize); // 取所有基环的最大值
        }

        return max(maxRingSize, sumChainSize);
    }
};

class Solution 
{
public:
    int maximumInvitations(vector<int>& g) 
    {
        int n = g.size();
        vector<int> indegree(n);
        for(int y : g)
        {
            ++indegree[y];
        }

        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            if(!indegree[i]) q.push(i);
        }        

        // depth[i]：不包括 i 在内，i 之前的最长链的长度
        vector<int> depth(n);
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            int y = g[x];
            depth[y] = max(depth[y], depth[x] + 1);
            if(--indegree[y] == 0) q.push(y);
        }

        // 此时 indegree[i] 大于 0，则说明 i 在环内
        int sumOfSmallRings = 0, bigRings = 0;
        for(int i = 0; i < n; ++i)
        {
            if(indegree[i] > 0)
            {
                int ringSize = 1;
                indegree[i] = 0; // 标记该基环已经访问过了
                for(int j = g[i]; j != i; j = g[j])
                {
                    ++ringSize;
                    indegree[j] = 0;
                }
                if(ringSize == 2) sumOfSmallRings += depth[i] + depth[g[i]] + 2;
                else bigRings = max(bigRings, ringSize);
            }
        }
        return max(sumOfSmallRings, bigRings);
    }
};